package cn.edu.cdu.argorithm.impl;

import cn.edu.cdu.argorithm.IRotateArray;

public class RotateArray {
    public static class Solution1 implements IRotateArray {
        @Override
        public void rotate(int[] nums, int k) {
            int n = nums.length;
            int[] arr  = new int[n];
            for (int i = 0; i < n; i++) {
                arr[(i + k) % n] = nums[i];
            }
            System.arraycopy(arr, 0, nums, 0, n);
        }
    }

    public static class Solution2 implements IRotateArray{
        @Override
        public void rotate(int[] nums, int k) {
            int n = nums.length;
            k %= n;
            int count = gcd(n, k);
            for (int i = 0; i < count; i++) {
                int currIndex = i, curr = nums[currIndex];
                do{
                    int nextIndex = (currIndex + k) % n;
                    int temp = nums[nextIndex];
                    nums[nextIndex] = curr;
                    currIndex = nextIndex;
                    curr = temp;
                }while (currIndex != i);
            }
        }

        public int gcd(int x, int y) {
            return y > 0 ? gcd(y, x % y) : x;
        }
    }

    public static class Solution3 implements IRotateArray{
        @Override
        public void rotate(int[] nums, int k) {
            int n = nums.length;
            k %= n;
            reverse(nums, 0, n - 1);
            reverse(nums,0, k - 1);
            reverse(nums, k, n - 1);
        }

        private void reverse(int[] nums, int start, int end){
            while(start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                ++start;
                --end;
            }
        }
    }
}
